/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhongfang
 *
 */
public class ErecttheFence {
	  class Point {
		      int x;
		      int y;
		      Point() { x = 0; y = 0; }
		      Point(int a, int b) { x = a; y = b; }
		  }
    public List<Point> outerTrees(Point[] points) {
    	List<Point> result=new ArrayList<>();
    	result.add(points[0]);
    	result.add(points[1]);
    	result.add(points[2]);
    	int i=3;
    	while (true) {
    		boolean in=isPointIn(result,points[i]);
    		i++;
    		if(in==false){
    			result.add(points[i]);
    			//删除每一个被包围的点
    			
    		}
    		break;
		}
        return null;
    }
    private boolean isPointIn(List<Point> result, Point point) {
    	int nCross=0;
    	int size=result.size();
    	for (int i = 0; i <result.size(); i++) {
			Point p1=result.get(i);
			Point p2=result.get((i+1)%size);
			if(p1.y==p2.y||point.y<Math.min(p1.y, p2.y)||point.y>=Math.max(p1.y, p2.y)){
				continue;
			}
			double x = (double)(point.y - p1.y) * (double)(p2.x - p1.x) / (double)(p2.y - p1.y) + p1.x;
			if ( x > point.x ) 
				nCross++; // 只统计单边交点 
		}
    	  return (nCross % 2 == 1); 
	}
	public static void main(String[] args) {
		
	}

}
